Cryptography I Week1
https://www.coursera.org/learn/crypto/home/week/1
Cource Overview
https://www.coursera.org/learn/crypto/lecture/lboqg/course-overview
1.5x くらいで聞くのがよさそう
no eavesdropping
no tampering
cipher
暗号化するアルゴリズムは公になっているもののほうがいい
Cryptography is not something you should try to invent yourself
What is Cryptography?
https://www.coursera.org/learn/crypto/lecture/ubmLN/what-is-cryptography
Crypto core
secret key establishment
secure communication
Digital signatures
Anonymous communication
Anonymous digital cash
double spending を防ぐ仕組みが必要
Protocols
Elections
Private auctions
Privately outsourcing computation
Zero knowledge
Alice が $ N=p \times qを知っているとする
Bob は N を知っている
Alice は N の factors (pとq)を知っていることを、pとqを伝えることなく証明できる
rigorous science
Precisely specify threat model
Propose a construction
Prove that breaking construction under threat mode will solve an underlying hard problem
History of Cryptography
https://www.coursera.org/learn/crypto/lecture/xAJaD/history-of-cryptography
Symmetric Ciphers
Encryption algo: E
Decryption algp: D
Using the same key K
Historic Examples
Substitution cipher
Caesar Cipher
Shift by 3
3文字ずつずらす
What is the size of key space in the substitution cipher assuming 26 letters?
そもそも階乗の計算の仕方とか忘れた
階乗とは、1 からある数までの連続する整数の積のこと
$ 3! = 1 \times 2 \times 3 = 6
factorial
How to break a substitution cipher
頻繁に出てくるアルファベット
e, t, a
頻繁に出てくる文字の組み合わせ
he, an, in, th
Vigener cipher
Roter Machine
エニグマとか
key は substitution table
ただし、どんどん変わっていく
Data Encryption Standard
DES
key space が小さい
64 bit key
使用すべきでない
AES
Salsa20
Discrete Probability (Crash Course)
https://www.coursera.org/learn/crypto/lecture/qaEcL/discrete-probability-crash-course
U: finite set
Universe
Probability distribution
Uniform distribution
同じ probability を全ての要素に assign
Point distribution at x0
Distribution vector
Events
subset of Universe
やばい、けっこうわからないぞ
example
最後の 2bit が11になるprobabilityは？
8bit: 00000000 - 11111111
$ 2^8 = 256
$ 2^6 = 64
00000011
The union bound
集合の確率？
Random Variables
The uniform random variable
note: 11 って 2進数だよ！
Randomized algorithms
<=> Deterministic algorithm
set of all possible outputs
Discrete Probability (Crash Course, Cont.)
https://www.coursera.org/learn/crypto/lecture/JkDRg/discrete-probability-crash-course-cont
Independence
XOR
bit-wise addition mod 2
Cryptography でたくさん出てくる
The birthday paradox
Information Theoretic Security and The One Time Pad
https://www.coursera.org/learn/crypto/lecture/cbnX1/information-theoretic-security-and-the-one-time-pad
cipher の定義
K, M, C
K
polynomial time
E
often randamized
The One Time Pad
very fast
long key
暗号化したいメッセージと同じ長さのkeyが必要
現実的に使うのは難しい
Information Theoretic Security
Shannon 1949
Basic idea: cipher text should reveal no "info about plain text
OTP has perfect secrecy
OPT: no CT only atttak
Perfect secrecy => key の長さがメッセージの長さよりも長い必要がある
=> hard to use in practice
#coursera #crypto